import entity.HuffNode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.TreeSet;

/**
 * @Author: wanqian
 * @Date: 2021/2/8 15:24
 */
public class HuffmanTreeDemo {

    public static int[] arr = {13, 7, 8, 3, 29, 6, 1};

    public static void main(String[] args) {

        HuffNode huffNode = huffmanTree2(arr);
        huffNode.preOrder();
    }

    /**
     * 生成huffman树
     *
     * @param arr
     * @return
     */
    public static HuffNode huffmanTree(int[] arr) {
        //将数组转换为List
        ArrayList<HuffNode> huffNodes = new ArrayList<>();
        for (int i : arr) {
            huffNodes.add(new HuffNode(i));
        }

        while (huffNodes.size() > 1) {
            //从大到小排序
            Collections.sort(huffNodes);
            //取出最小的两个节点
            HuffNode leftNode = huffNodes.remove(0);
            HuffNode rightNode = huffNodes.remove(0);
            //生成一个父节点并放入List
            HuffNode parent = new HuffNode(leftNode, rightNode);
            huffNodes.add(parent);
        }
        return huffNodes.get(0);
    }

    /**
     * 生成huffman树(利用TreeSet实现)
     *
     * @param arr
     * @return
     */
    public static HuffNode huffmanTree2(int[] arr) {

        TreeSet<HuffNode> huffNodes = new TreeSet<>();
        for (int i : arr) {
            huffNodes.add(new HuffNode(i));
        }

        while (huffNodes.size() > 1) {
            //取出最小的两个节点
            HuffNode leftNode = huffNodes.pollFirst();
            HuffNode rightNode = huffNodes.pollFirst();
            //生成一个父节点并放入List
            HuffNode parent = new HuffNode(leftNode, rightNode);
            huffNodes.add(parent);
        }
        return huffNodes.first();
    }
}
